package simple;

/**
 给定一个升序排序的数组，将其转化为平衡二叉搜索树（BST）.
 平衡二叉搜索树指树上每个节点 node 都满足左子树中所有节点的的值都小于 node 的值，右子树中所有节点的值都大于 node 的值，并且左右子树的节点数量之差不大于1
 数据范围：0 \le n \le 100000≤n≤10000，数组中每个值满足 |val| \le 5000∣val∣≤5000
 进阶：空间复杂度 O(n)O(n) ，时间复杂度 O(n)O(n)
 示例1
 输入：
 [-1,0,1,2]
 返回值：
 {1,0,2,-1}
 * @author WangZhiJian
 * @since 2022/1/14
 */
public class 将升序数组转化为平衡二叉搜索树 {
    /**
     *
     * @param num int整型一维数组
     * @return TreeNode类
     */
    public TreeNode sortedArrayToBST (int[] num) {
        return num == null ? null : sortedArrayToBST(num,0,num.length-1);
    }

    public TreeNode sortedArrayToBST (int[] num,int left,int right) {
        // 递归结束
        if(left > right)
            return null;
        // 根节点
        int mid = (right + left + 1) / 2;
        TreeNode treeNode = new TreeNode();
        treeNode.val = num[mid];
        // 左子树
        treeNode.left = sortedArrayToBST(num,left,mid-1);
        // 柚子树
        treeNode.right = sortedArrayToBST(num,mid+1,right);
        return treeNode;
    }

      public static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
      }
}
